﻿/////////////////////////////////////////////////////////////////////////
//                                                                     //
//    MTGProject - A Magic The Gathering Networked Environment         //
//                                                                     //
//  Copyright (c) 2008-2009 by The MTGProject Team (CSC230 & MAT227)   //
//                                                                     //
// This file is part of MTGProject.                                    //
//                                                                     //
// MTGProject is free software; you can redistribute it and/or         //
// modify it under the terms of the GNU Lesser General Public          //
// License as published by the Free Software Foundation; either        //
// version 3 of the License, or (at your option) any later version.    //
//                                                                     //
// This library is distributed in the hope that it will be useful,     //
// but WITHOUT ANY WARRANTY; without even the implied warranty of      //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the       //
// GNU Lesser General Public License for more details.                 //
//                                                                     //
// You should have received a copy of the GNU Lesser General Public    //
// License along with this library; if not, write to the Free Software //
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA           //
// 02111-1307, USA, or contact the author(s):                          //
//                                                                     //
// Ruben Acuna <flyingfowlsoftware@earthlink.net>                      //
// Chris Watson <the5thdimension@hotmail.com>                          //
//                                                                     //
/////////////////////////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Text;

namespace MTGProject
{
    class PlayerControllerAIClassic : PlayerController
    {
        #region variables

        private Player puppet;
        private LinkedList<CardCreature> possibleAttackers;

        #endregion

        #region properties

        public override Player Puppet
        {
            get { return puppet; }
            set { puppet = value; }
        }

        public override bool IsConnected
        {
            get { return true; }
            set { }
        }

        #endregion

        #region consturctor

        public PlayerControllerAIClassic(Player puppet, string deck)
        {
            Puppet = puppet;

            Puppet.Deck = CardIO.LoadXMLDeck(deck);
        }

        #endregion

        #region methods

        public override void PhaseMain()
        {
            System.Console.WriteLine("  My health is: " + Puppet.Health);

            //Play a land
            foreach (ICard card in Puppet.Hand.Cards)
                if (card is CardLand)
                {
                    Puppet.PlayCard(card);
                    break;
                }

            //Tap all land.
            foreach (IPermanent card in Puppet.Permanents.Cards)
                if (card is CardLand && !card.IsTapped)
                    Puppet.TapCard(card);

            //Play all lands possible.
            ICard[] hand = new ICard[Puppet.Hand.Cards.Count];
            Puppet.Hand.Cards.CopyTo(hand, 0);
            for (int x = 0; x < hand.Length; x++)
            {
                ICard card = hand[x];
                if (card is CardCreature && UtilMagic.CanAffordCost(card.Cost, Puppet.ManaPool))
                    Puppet.PlayCard(card);
            }
        }

        public override int PhaseDefense(LinkedList<CardCreature> attackingCreatures)
        {
            return 0;
        }

        public override void OnLose()
        {
            // do nothing
        }

        public override void OnWin()
        {
            // do nothing
        }

        public override ICard SelectCard(LinkedList<ICard> cards)
        {
            return SelectCard(cards, "");
        }

        public override ICard SelectCard(LinkedList<ICard> cards, string message)
        {
            if (message.Length > 0)
                Tell(message);

            return cards.First.Value;
        }

        public override void Tell(string message)
        {
            System.Console.WriteLine("  " + Puppet.Name + " heard: " + message);
        }

        #endregion

        #region combat phase methods

        public override void PhaseCombatStart()
        {
            possibleAttackers = new LinkedList<CardCreature>();

            foreach (IPermanent permanent in Puppet.Permanents.Cards)
                if (permanent is CardCreature && !permanent.IsTapped && !((CardCreature)permanent).IsSick)
                    possibleAttackers.AddLast((CardCreature)permanent);
        }

        public override CardCreature PhaseCombatRequestAttackingCreature()
        {
            CardCreature creature = null;

            if (possibleAttackers.Count > 0)
            {
                creature = possibleAttackers.First.Value;
                possibleAttackers.Remove(creature);
            }
            return creature;
        }

        public override void PhaseCombatEnd()
        {
            //do nothing
        }

        #endregion
    }

    /// <summary>
    /// Implements a decent AI for playing MTG. It is based off of a modified
    /// min-max tree algorithm and can detect the probability that certain
    /// cards will be drawn. Note that this AI only supports creature decks
    /// without multicolor cards.
    /// </summary>
    class PlayerControllerAI : PlayerController
    {
        #region variables

        //The Puppet.
        private Player puppet;

        //Used for combat phase.
        private LinkedList<CardCreature> possibleAttackers;

        //Used for card predictions.
        private LinkedList<ICard> myCompleteDeck;
        private CardPool myPossibleCards;

        #endregion

        #region properties

        /// <summary>
        /// Returns the Puppet currently controlled by the AI.
        /// </summary>
        public override Player Puppet
        {
            get { return puppet; }
            set { puppet = value; }
        }

        /// <summary>
        /// Returns the AI's connection state for the GameServer, always true.
        /// </summary>
        public override bool IsConnected
        {
            get { return true; }
            set { }
        }

        #endregion

        #region constuctor

        public PlayerControllerAI(Player puppet, string deck)
        {
            Puppet = puppet;

            Puppet.Deck = CardIO.LoadXMLDeck(deck);
        }
        #endregion

        #region methods

        /// <summary>
        /// Returns the name of the best land card to play based on the contents
        /// of the AI's hand. This is calculated by finding the ratio of how many
        /// lands in play vs in the hand. The lowest ratio will be put into play
        /// in an attempt to balance lands against possible plays.
        /// For example, if a hand contains 12 Forests and 12 Mountains worth of
        /// spells, and two Forests are in play, the ration for Green mana would
        /// be .167, while the ration of Red would be .083, telling the AI that
        /// it needs more Red mana to efficiently play this deck.
        /// While this is a working strategy, there are limitations. For example,
        /// this strategy assumes a proper balance of mana to permanents of same
        /// color, which is an issue of deck creation, but more importantly, this
        /// assumes that the requirements for the AI to play a permanent is the
        /// same as the ratio of the deck, which of course is not the case since
        /// cards are chosen at random. Upon playing this strategy, the AI does
        /// seem to work efficiently, and time was better spent on more complex
        /// problems.
        /// Returns an empty string if there is no land we can play.
        /// </summary>
        /// <returns>Name of a card or empty for no card.</returns>
        public string GetBestLand()
        {
            string idealCard = "";
            LinkedList<float> landRatios = new LinkedList<float>();
            float handManaWhite = 0;
            float handManaBlue = 0;
            float handManaBlack = 0;
            float handManaRed = 0;
            float handManaGreen = 0;
            float ratioManaWhite = 0;
            float ratioManaBlue = 0;
            float ratioManaBlack = 0;
            float ratioManaRed = 0;
            float ratioManaGreen = 0;
            float lowestRatio = 0;

            System.Console.WriteLine("  " + Puppet.Name + " is thinking about land...");

            //Finds ratio of lands in play
            //*designed for single colored cards*

            //Counts the total magic cost points for each color.
            //Since lands have no cost we can access the complete hand instead of having
            //to sort out the non-land cards.
            handManaWhite = CountManaCostByColor(Puppet.Hand.Cards, ManaColor.WHITE);
            handManaBlue = CountManaCostByColor(Puppet.Hand.Cards, ManaColor.BLUE);
            handManaBlack = CountManaCostByColor(Puppet.Hand.Cards, ManaColor.BLACK);
            handManaRed = CountManaCostByColor(Puppet.Hand.Cards, ManaColor.RED);
            handManaGreen = CountManaCostByColor(Puppet.Hand.Cards, ManaColor.GREEN);

            //calculate ratio of lands in play vs. in hand
            if (handManaBlack != 0)
            {
                ratioManaBlack = CountLandByColor(Puppet.Permanents.Cards, ManaColor.BLACK) / handManaBlack;
                landRatios.AddLast(ratioManaBlack);
                System.Console.WriteLine("    My black mana ratio is " + ratioManaBlack + ".");
            }
            if (handManaBlue != 0)
            {
                ratioManaBlue = CountLandByColor(Puppet.Permanents.Cards, ManaColor.BLUE) / handManaBlue;
                landRatios.AddLast(ratioManaBlue);
                System.Console.WriteLine("    My blue mana ratio is " + ratioManaBlue + ".");
            }
            if (handManaGreen != 0)
            {
                ratioManaGreen = CountLandByColor(Puppet.Permanents.Cards, ManaColor.GREEN) / handManaGreen;
                landRatios.AddLast(ratioManaGreen);
                System.Console.WriteLine("    My green mana ratio is " + ratioManaGreen + ".");
            }
            if (handManaRed != 0)
            {
                ratioManaRed = CountLandByColor(Puppet.Permanents.Cards, ManaColor.RED) / handManaRed;
                landRatios.AddLast(ratioManaRed);
                System.Console.WriteLine("    My red mana ratio is " + ratioManaRed + ".");
            }
            if (handManaWhite != 0)
            {
                ratioManaWhite = CountLandByColor(Puppet.Permanents.Cards, ManaColor.WHITE) / handManaWhite;
                landRatios.AddLast(ratioManaWhite);
                System.Console.WriteLine("    My white mana ratio is " + ratioManaWhite + ".");
            }

            //FIXME: Possible bug, if the hand contains no cards with a cost, none of
            //       the branchs above will trigger. GetLowestFloat will then crash
            //       because the list we pass it has no elements.

            do
            {
                lowestRatio = UtilMath.GetLowestFloat(landRatios);

                if (lowestRatio == ratioManaBlack)
                    foreach (ICard card in Puppet.Hand.Cards)
                        if (card is CardLand && card.Colors.First.Value == ManaColor.BLACK)
                            idealCard = card.Name;
                if (lowestRatio == ratioManaWhite)
                    foreach (ICard card in Puppet.Hand.Cards)
                        if (card is CardLand && card.Colors.First.Value == ManaColor.WHITE)
                            idealCard = card.Name;
                if (lowestRatio == ratioManaBlue)
                    foreach (ICard card in Puppet.Hand.Cards)
                        if (card is CardLand && card.Colors.First.Value == ManaColor.BLUE)
                            idealCard = card.Name;
                if (lowestRatio == ratioManaRed)
                    foreach (ICard card in Puppet.Hand.Cards)
                        if (card is CardLand && card.Colors.First.Value == ManaColor.RED)
                            idealCard = card.Name;
                if (lowestRatio == ratioManaGreen)
                    foreach (ICard card in Puppet.Hand.Cards)
                        if (card is CardLand && card.Colors.First.Value == ManaColor.GREEN)
                            idealCard = card.Name;

                landRatios.Remove(lowestRatio);

            } while (landRatios.Count > 0 && idealCard == "");

            if (idealCard != "")
                System.Console.WriteLine("    I think it would be best to play a " + idealCard + ".");
            else
                System.Console.WriteLine("    I don't think I can play a land.");

            return idealCard;
        }

        /// <summary>
        /// Sets up a few lists for predicting the AIs next card draws. A list
        /// containing the complete AI's deck is built as well as a list containing
        /// one of each card type within the deck.
        /// </summary>
        public void PrepareMyCardPredictions()
        {
            myCompleteDeck = new LinkedList<ICard>();
            myPossibleCards = new CardPool(Zone.OTHER);

            //The complete contains everything in the remaining deck.
            foreach (ICard card in Puppet.Deck.Cards)
                myCompleteDeck.AddLast(card);

            //The complete contains everything in the AIs hand.
            foreach (ICard card in Puppet.Hand.Cards)
                myCompleteDeck.AddLast(card);

            foreach (ICard card in myCompleteDeck)
            {
                bool newCard = true;

                //Loop over each card in the complete deck, if myPossibleCards
                //doesn't contain a card with that cards name, it is added to
                //myPossibleCards.

                foreach (ICard possibleCard in myPossibleCards.Cards)
                    if (possibleCard.Name.Equals(card.Name))
                        newCard = false;

                if (newCard)
                    myPossibleCards.AddCard(card);
            }
        }

        /// <summary>
        /// This function attempts to predict the composition of the enemy's deck
        /// based on the cards they have played. In the future, this function will
        /// also be used to predict their next card draw for the min-max tree.
        /// </summary>
        public void UpdateEnemyCardPredictions()
        {
            CardPool enemyDeck = new CardPool(Zone.OTHER);
            CardPool enemyKnownCards = new CardPool(Zone.OTHER);

            //Any card among the enemy's permanents is a card in their deck.
            foreach (ICard card in Puppet.Enemy.Permanents.Cards)
                enemyKnownCards.AddCard(card);

            //Any card in the enemy's graveyard is a card in their deck.
            foreach(ICard card in Puppet.Enemy.Graveyard.Cards)
                enemyKnownCards.AddCard(card);

            while (enemyKnownCards.Cards.Count > 0)
            {
                string cardName = enemyKnownCards.Cards.First.Value.Name;
                int cardCount = enemyKnownCards.countCard(cardName);

                //If it appears to be an ordinary card, i.e. non-land because
                //less than 5 are in play, assume there are four copies in their deck.
                if(cardCount < 5)
                    for(int x = 0; x < 4; x++)
                        //FIXME: This may screw up the state!!!!!!!!!!!!!!!!!!!!!
                        enemyDeck.AddCard(enemyKnownCards.GetCardByName(cardName));  
                //In any other case the card must be a land (or relentless rats),
                //without more complicated code the best we can do is assume they
                //have as many copies of that card as have entered play.
                else
                    for (int x = 0; x < cardCount; x++)
                        //FIXME: This may screw up the state!!!!!!!!!!!!!!!!!!!!!
                        enemyDeck.AddCard(enemyKnownCards.GetCardByName(cardName));

                //Remove any duplicates of the card (using the name) from known cards.
                for(int x = 0; x < cardCount; x++)
                    enemyKnownCards.RemoveCard(enemyKnownCards.GetCardByName(cardName));
            }

            System.Console.WriteLine("  " + Puppet.Name + " thinks " +
                                     Puppet.Enemy.Name + "'s deck is: ");
            DisplayCardPoolCounted(enemyDeck, "    ");


        }

        /// <summary>
        /// Returns the best (fastest to win) possible combination of creatures
        /// to play. See getRank().
        /// </summary>
        /// <returns>A list containing the names of the best creatures to play.</returns>
        public LinkedList<string> getBestCreatures()
        {
            LinkedList<string> bestCombination = new LinkedList<string>();
            LinkedList<LinkedList<string>> possibleCombinations 
                                             = new LinkedList<LinkedList<string>>();
            float bestRank = 0;
            int currentCombination = 1;

            //Create a list of all possible plays in the current game state.
            possibleCombinations 
                = PossibleCreatures(GetProjectedManaPool(Puppet.Permanents), Puppet.Hand);
            
            //Create a new GameState from the current game.
            AIVirtualGameState currentState = new AIVirtualGameState();
            currentState.AIHealth = Puppet.Health;
            currentState.AIHand = Puppet.Hand.clone();
            currentState.AIPermanents = Puppet.Permanents.clone();
            currentState.AIDeck = Puppet.Deck.clone();
            currentState.EnemyHealth = Puppet.Enemy.Health;
            currentState.EnemyPermanents = Puppet.Enemy.Permanents.clone();

            //Expand the tree for each combination.
            //TODO: This is very similar to get rank, can they should be merged?
            //      The only reason this is seperate is because we need to track
            //      the combination that resulted in a certain (best) rank.
            foreach (LinkedList<string> combination in possibleCombinations)
            {
                AIVirtualGameState combinationState = currentState.clone();
                float combinationRank = 0;
                
                System.Console.WriteLine("\n__Ranking combination #" + 
                                         currentCombination + "__");

                DisplayStringListShort("  Play", combination);

                //A land has already been played in MainPhase() using
                //getBestLand, so there is no need to play one again.

                //Simulate the effect of AI attacking with all creatures.
                DisplayCardPoolCreaturesShort("  Attackers", combinationState.AIPermanents);
                foreach (ICard creature in combinationState.AIPermanents.Cards)
                    if (creature is CardCreature)
                    {
                        combinationState.EnemyHealth -= ((CardCreature)creature).Power;
                    }

                //Simulate playing the cards.
                foreach (string creature in combination)
                {
                    combinationState.AIPermanents.AddCard(combinationState.AIHand.GetCardByName(creature));
                    combinationState.AIHand.RemoveCard(combinationState.AIHand.GetCardByName(creature));
                }

                //base case 1, AI lost.
                //We shouldn't to check if the AI dies (like in getRank) because
                //we don't simulate the enemy's damage here. However, this code 
                //still runs sometimes. FIXME: Bug in core :(
                if (combinationState.AIHealth <= 0)
                {
                    System.Console.WriteLine("  Rank: 0 (AI death)");
                    combinationRank = 0;
                }
                //base case 2, AI won.
                else if (combinationState.EnemyHealth <= 0)
                {
                    System.Console.WriteLine("  Rank: 1 (enemy death)");
                    combinationRank = 1;
                }
                //This isn't a final state, we need to find the sum of the sub-
                //gamestates we generate.
                else
                {
                    combinationRank = GetRank(combinationState, 1);
                }

                System.Console.WriteLine("\n  Total Rank: " + combinationRank);

                //Check if the rank of this combination is better than any
                //previous ones.
                if (combinationRank >= bestRank)
                {
                    bestRank = combinationRank;
                    bestCombination = combination; //FIXME: Reference weirdness?
                }

                System.Console.WriteLine("\n__Finished ranking #" + currentCombination + "__");

                currentCombination++;
            }

            if (possibleCombinations.Count == 0)
                throw new Exception("getBestCreatures() found no combinations.");
            else
                DisplayStringListShort("Best rank (" + bestRank + ")",
                                       bestCombination);

            return bestCombination;
        }

        /// <summary>
        /// This function will build a modified power set from the creatures in
        /// a CardPool. Each of it's subsets is a possible combination of cards
        /// played. Duplicates will be removed. Duplicates will be created when
        /// each combination is evaluated and only allows for cards which can be
        /// played based on their mana cost. For example, you may have a combination
        /// of 3 cards to be played, but the total mana cost may exceed what is
        /// available. Assume there are now 2 cards which can be played, that
        /// combination already exists, and should be dealt with to require less processing.
        /// </summary>
        /// <param name="currentManaPool">The maximum mana that can be used.</param>
        /// <param name="hand">CardPool with creatures that may be played.</param>
        /// <returns></returns>
        public LinkedList<LinkedList<string>> PossibleCreatures(LinkedList<ManaColor> manaPool,
                                                                CardPool hand)
        {
            //TODO: How do we work spell combinations into this?

            LinkedList<LinkedList<string>> powerSet 
                = new LinkedList<LinkedList<string>>();
            CardPool allCreatures = new CardPool(Zone.OTHER);
            ICard[] allCreaturesArray = null;
            int totalSubsets;

            foreach (ICard card in hand.Cards)
                if (card is CardCreature)
                    allCreatures.AddCard(card);

            allCreaturesArray = new ICard[allCreatures.Cards.Count];

            allCreatures.Cards.CopyTo(allCreaturesArray, 0);
            totalSubsets = (int)Math.Pow(2, allCreaturesArray.Length);

            //Now we start building the combinations of creatures. Since this is
            //basically a power set, it's cardinality will be 2^creatures. The
            //current subset from 0 to n is is tracked by currentSubset.

            for (int currentSubset = 1; currentSubset < totalSubsets; currentSubset++)
            {
                LinkedList<string> subset = new LinkedList<string>();
                LinkedList<ManaColor> subsetManapool = UtilMagic.CloneEnums<ManaColor>(manaPool);

                //At this point we have the number of the subset we need to generate. The
                //cards in it can be found by looking at the bits of subset number. Let's
                //assume we have two creatures, C1 & C2, look at the following truth table:
                //C2 C1 #
                //0  0  0
                //0  1  1 
                //1  0  2
                //1  1  3 <--- 2^2 = 4 but we start at 0 so 3.

                //The bit pattern for the subset number can be broken down as above. Once
                //it is broken down we can use the bit to determine if a creature should
                //be in a given subset.
                
                //Basically, we use a bit shift to get us to the right column and then
                //loop over the rows using modulus to check if the card is in the subset.

                for (int bitShift = 0; bitShift < allCreaturesArray.Length; bitShift++)
                    if (((currentSubset >> bitShift) % 2) == 1)
                        //At this point we know the creature is suppose to be in
                        //the subset but there's no point in adding it unless we
                        //can play it. Because we do this, will end up with
                        //duplicate subsets to prune later on.
                        if (UtilMagic.CanAffordCost(allCreaturesArray[bitShift].Cost, subsetManapool))
                        {
                            subset.AddLast(allCreaturesArray[bitShift].Name);

                            //For each subset we maintain a manaPool, so if we
                            //remove the cost of the cards we add to a subset, all
                            //subsets will be playable (since we check CanAfford).

                            UtilMagic.PayCost(allCreaturesArray[bitShift].Cost, subsetManapool);
                        }

                //There are bound to be plently of empty sets so don't bother
                //adding them to powerSet.
                //WARNING: This will also remove THE empty set.
                if (subset.Count > 0)
                    powerSet.AddLast(subset);
            }

            //Add the empty set if no other combinations were found. If you can
            //play a creature, it is never better to play nothing so we skip it
            //then. Skipping it also prevents the infinite recursion that results
            //from the possibility of the AI continually playing nothing and the
            //enemy not have any card in play to kill the AI (one of the base cases).
            if(powerSet.Count == 0)
                powerSet.AddLast(new LinkedList<string>());


            //At this point we have list containing all the possible combinations
            //of the cards. However, when we build the subset we also check to see
            //if the AI can afford to play it. If they don't, the card is not
            //added to the subset. Because of this, some of the subsets will end
            //up being duplicates. For speed (127 combinations vs ~4) reasons, we
            //should prune these from the tree.

            PrunePossibleSpells(powerSet);

            return powerSet;
        }

        /// <summary>
        /// Given a list containing lists of combinations of spells, this function
        /// will remove any duplicate combinations within the list.
        /// 
        /// Please don't complain that this function is slow - at least it works.
        /// </summary>
        /// <param name="allCombinations">A list with all possible spells combos.</param>
        private void PrunePossibleSpells(LinkedList<LinkedList<string>> allCombinations)
        {
            LinkedList<LinkedList<string>> uniqueCombinations 
                                             = new LinkedList<LinkedList<string>>();

            //We start by picking the first combination in the remaining combinations,
            //then we add it to the unique list and remove any matching combinations
            //from the remaining combinations. Rinse and repeat until there are no
            //remaining combinations.

            while (allCombinations.Count > 0)
            {
                LinkedList<string> currentCombination = allCombinations.First.Value;
                LinkedList<LinkedList<string>> duplicateCombinations
                                                 = new LinkedList<LinkedList<string>>();

                uniqueCombinations.AddLast(currentCombination);
                allCombinations.Remove(currentCombination);

                foreach (LinkedList<string> possibleDuplicate in allCombinations)
                {
                    //The possibleDuplicate must have the card count as the
                    //combination to be a duplicate.
                    if (possibleDuplicate.Count == currentCombination.Count)
                    {
                        //Make a copy of possibleDuplicate.
                        LinkedList<string> copyPossibleDuplicate
                                             = new LinkedList<string>();
                        foreach (string card in possibleDuplicate)
                            copyPossibleDuplicate.AddLast(card);

                        //Becomes true if copyPossibleDuplicate does not contain a
                        //spell from currentCombination (i.e. copy is different).
                        bool missingSpell = false;

                        //To find out if the combination is a duplicate, we try and
                        //remove every card from the unique list from the possible
                        //duplicate. If the possible duplicate contains all the
                        //cards (i.e. no missing cards) and after we removed the cards
                        //from it, it had no cards remaining, then it is duplicate.

                        foreach (string card in currentCombination)
                        {
                            string foundCard = null;

                            foreach (string cardDuplicate in copyPossibleDuplicate)
                            {
                                if (card.Equals(cardDuplicate))
                                    foundCard = cardDuplicate;
                            }

                            if(foundCard == null)
                                missingSpell = true;
                            else
                                copyPossibleDuplicate.Remove(foundCard);
                        }

                        if (copyPossibleDuplicate.Count == 0 && !missingSpell)
                        {
                            duplicateCombinations.AddLast(possibleDuplicate);
                        }
                    }
                }

                foreach (LinkedList<string> duplicate in duplicateCombinations)
                {
                    allCombinations.Remove(duplicate);
                }
            }

            //allCombinations will be empty at this, so we copy everything from
            //uniqueCombinations into it.
            foreach (LinkedList<string> unique in uniqueCombinations)
                allCombinations.AddLast(unique);
        }

        /// <summary>
        /// Returns the rank of a given game state using a modified min-max
        /// algorithm. Ranks range between 0 (sure loss) and 1 (sure win), where
        /// higher is better. It is assumed that the GameState is one right after
        /// the AI's turn has ended. To calculate the rank of a state, the
        /// function recursively simulates new game states until each one has
        /// reached a win or loss. A win counts as 1 and a loss as 0, as the stack
        /// unfolds, the ranks will be weighed according to how deep they are.
        /// </summary>
        /// <param name="currentState">GameState to rank.</param>
        /// <param name="depth">Depth of this GameState from actual state.</param>
        /// <returns>Rank of GameState.</returns>
        public float GetRank(AIVirtualGameState currentState, int depth)
        {
            string pad = "";
            float stateRank = 0;

            //Display currentState with a whitespace pad that indicates the
            //depth of the this leaf.
            for(int x = 0; x < depth; x++)
                pad += "  ";

            System.Console.WriteLine(pad + "Calculating Rank...");
            System.Console.WriteLine(pad + "Depth: " + depth);
            System.Console.WriteLine(pad + "AI HP: " + currentState.AIHealth);
            DisplayCardPoolCreaturesShort(pad + "AI Perms", currentState.AIPermanents);
            System.Console.WriteLine(pad + "Enemy HP: " + currentState.EnemyHealth);
            DisplayCardPoolCreaturesShort(pad + "Enemy Att.", currentState.EnemyPermanents);

            //START -- SIMULATE ENEMY'S TURN

            //TODO: We need to simulate the enemy playing or drawing cards.

            //Update the AI's health with the effect of being attacked by all of
            //the enemy's creatures.
            foreach (ICard creature in currentState.EnemyPermanents.Cards)
                if (creature is CardCreature)
                {
                    currentState.AIHealth -= ((CardCreature)creature).Power;
                }

            //Check base case: AI lost.
            if (currentState.AIHealth <= 0)
            {
                System.Console.WriteLine(pad + "  Leaf Rank: 0 (AI death)");
                return 0; //No futher calculations are necessary - AI is dead.
            }

            //END -- SIMULATE ENEMY'S TURN

            //At this point, the AI has survived the attack by the other player.
            //We now need to update the currentState by drawing a new card and
            //playing a card. After that, we can build the list of our leaf card
            //combinations and recurse.

            //START -- SIMULATE AI's TURN

            //Simulate drawing a card.
            //FIXME: In this case we are drawing the actual card that we will draw,
            //       we should use the predict next card function instead.
            System.Console.WriteLine(pad + "Drew Card: " +
                                     currentState.AIDeck.Cards.First.Value.Name);
            currentState.AIHand.AddCard(currentState.AIDeck.Cards.First.Value);
            currentState.AIDeck.RemoveCard(currentState.AIDeck.Cards.First.Value);

            //Play land. (getBestLand must be retooled to use it here.)
            foreach(ICard card in currentState.AIHand.Cards)
            {
                if(card is CardLand)
                {
                    System.Console.WriteLine(pad + "Play Land: " + card.Name);
                    currentState.AIHand.RemoveCard(card);
                    currentState.AIPermanents.AddCard(card);
                    break;
                }
            }

            //Build a list of all possible card combinations and store it as a
            //list in a list called possibleCombinations.
            LinkedList<LinkedList<string>> possibleCombinations
                = PossibleCreatures(GetProjectedManaPool(currentState.AIPermanents),
                                    currentState.AIHand.clone());

            //This loops over all the possible combinations of card plays and
            //creates a new leaf state where each combination was played.
            foreach (LinkedList<string> possibleCombination in possibleCombinations)
            {
                //Create a new gamestate from the current state.
                AIVirtualGameState newState = currentState.clone();

                //Update state with effect of the AI attacking with all creatures.
                //TODO: Why wasn't this moved out of the foreach?
                foreach (ICard creature in newState.AIPermanents.Cards)
                    if (creature is CardCreature)
                    {
                        newState.EnemyHealth -= ((CardCreature)creature).Power;
                    }

                //Base case: AI killed enemy - don't add to leaf list.
                if (newState.EnemyHealth <= 0)
                {
                    System.Console.WriteLine(pad + "  Leaf Rank: 1 (enemy death)");
                    stateRank += 1.0f;
                }
                else //We didn't trigger a base case and need to recurse to find our rank.
                {
                    System.Console.WriteLine(pad + "  Creating Leaf...");

                    //Update state by playing the creatures in this combination.
                    //In the case that we don't play any cards, Play: N/A will print.
                    DisplayStringListShort(pad + "  Play", possibleCombination);
                    foreach (string creature in possibleCombination)
                    {
                        newState.AIPermanents.AddCard(newState.AIHand.GetCardByName(creature));
                        newState.AIHand.RemoveCard(newState.AIHand.GetCardByName(creature));
                    }

                    //List AI attackers, the damage they dealt was already simulated.
                    DisplayCardPoolCreaturesShort(pad + "  Attackers", newState.AIPermanents);

                    //++ doesn't work here because it has lower priority than +=?!?
                    stateRank += GetRank(newState, depth + 1);
                }
            }

            //END -- SIMULATE AI's TURN

            //At this point, the current rank of this state is the sum of the
            //ranks of all leaf states. We now reweigh each leaf rank based on
            //how many total leafs were added (since /count works as if it was
            //factored out).
            stateRank = stateRank / (possibleCombinations.Count);

            System.Console.WriteLine(pad + "Leaf Rank: " + stateRank);

            return stateRank;
            
        }

        /// <summary>
        /// Called when it is the AI's main phase. The AI will play the best land
        /// possible and then play the combination of creatures most likely to
        /// win the game. Statistics about the AI at the beginning of the turn
        /// will be displayed, as well as predictions about it’s next turn.
        /// </summary>
        public override void PhaseMain()
        {
            string bestLand = "";
            LinkedList<string> creaturesToPlay = new LinkedList<string>();

            //TODO: We really should have a function in the player controller class
            //      that runs once at the start.

            //On the first turn, set up for future card predictions.
            if (myCompleteDeck == null && myPossibleCards == null)
                PrepareMyCardPredictions();

            //Display the AI's state at the begining of the turn.
            System.Console.WriteLine("  " + Puppet.Name + " is thinking...");
            System.Console.WriteLine("  My health is: " + Puppet.Health);
            System.Console.WriteLine("  My hand contains: ");
            DisplayCardPoolCounted(Puppet.Hand, "    ");
            System.Console.WriteLine("  My permanents are: ");
            DisplayCardPoolCounted(Puppet.Permanents, "    ");

            //Play the best possible land using the AI in GetBestLand().
            bestLand = GetBestLand();
            if (bestLand != "") 
                Puppet.PlayCard(Puppet.Hand.GetCardByName(bestLand));

            //Find the best possible combinations of creatures to play.
            creaturesToPlay = getBestCreatures();

            //Tap exact land needed to play each creature in creaturesToPlay.
            foreach (string creature in creaturesToPlay)
            {
                foreach (ManaColor color in Puppet.Hand.GetCardByName(creature).Cost)
                    foreach (ICard land in Puppet.Permanents.Cards)
                        if (land is CardLand 
                            && !((CardLand)land).IsTapped 
                            && (land.Colors.First.Value == color
                                || color == ManaColor.NONE))
                        {
                            Puppet.TapCard((IPermanent)land);
                            break;
                        }
            }

            //Play each creature in creaturesToPlay.
            foreach (string creature in creaturesToPlay)
                Puppet.PlayCard(Puppet.Hand.GetCardByName(creature));

            //TODO: Tapping land and then playing the card is somewhat fragile.
            //      There is always a chance that PayCost() will use a ManaColor
            //      we need to play another card. Find some way to make this better.

            //ENABLE ME!!!
            System.Console.WriteLine("  " + Puppet.Name + " is thinking about the next round...");

            UtilAI.PredictNextDraw(myCompleteDeck, myPossibleCards, Puppet.Hand,Puppet.Graveyard);
            UpdateEnemyCardPredictions();
        }

        /// <summary>
        /// Called when the AI is being attacked by the enemy (technically in the
        /// enemy's combat phase). Nobody's quite sure how this function works.
        /// </summary>
        /// <param name="attackingCreatures">List of creatures attacking the AI.</param>
        /// <returns>Unknown.</returns>
        public override int PhaseDefense(LinkedList<CardCreature> attackingCreatures)
        {
            //TODO: Write awesome blocking code once Ruben remembers how this works.

            return 0;
        }

        /// <summary>
        /// Called when the AI has lost the game. It is not necessary for the AI
        /// to functon.
        /// </summary>
        public override void OnLose()
        {
            // Do nothing.
        }

        /// <summary>
        /// Called when the AI has won the game. It is not necessary for the AI
        /// to functon.
        /// </summary>
        public override void OnWin()
        {
            // Do nothing.
        }

        /// <summary>
        /// Called whenever a game state or sell requires the AI to choose a
        /// card from a CardPool. Always returns the first card in the list.
        /// </summary>
        /// <param name="cards">Cards to choose from.</param>
        /// <returns>Card chosen.</returns>
        public override ICard SelectCard(LinkedList<ICard> cards)
        {
            return SelectCard(cards, "");
        }
        public override ICard SelectCard(LinkedList<ICard> cards, string message)
        {
            if(message.Length > 0)
                Tell(message);

            return cards.First.Value;
        }

        /// <summary>
        /// Called when the AI receives a text message. At the moment, it prints
        /// the text to console for debugging.
        /// </summary>
        /// <param name="message">Text sent to AI.</param>
        public override void Tell(string message)
        {
            //TODO: Use this to get feedback about the environment from the server.

            System.Console.WriteLine("  " + Puppet.Name + " heard: " + message);
        }

        #endregion

        #region combat phase methods

        /// <summary>
        /// Called when the AI's combat turn is about to start. Builds a list of all
        /// possible creatures that the AI can attack with. Possible attackers are
        /// those creatures that are not tapped or suffering from summoning sickness.
        /// </summary>
        public override void PhaseCombatStart()
        {
            possibleAttackers = new LinkedList<CardCreature>();

            foreach (IPermanent permanent in Puppet.Permanents.Cards)
                if (permanent is CardCreature && !permanent.IsTapped && !((CardCreature)permanent).IsSick)
                    possibleAttackers.AddLast((CardCreature)permanent);
        }

        /// <summary>
        /// Called during the AI's combat phase to request an attacking creature.
        /// The AI will send all of the creatures in the possibleAttackers list
        /// built by PhaseCombatStart().
        /// </summary>
        /// <returns>A creature the AI is using to attack with.</returns>
        public override CardCreature PhaseCombatRequestAttackingCreature()
        {
            //The MTGCore will continue calling this function until it receives
            //'null', then it assumes that the PlayerController has listed all of
            //the creatures it is attacking with. The way this is set up, we send
            //each creature in possibleAttackers one at a time until there is no
            //more in the list, then the null will be sent automatically.

            CardCreature creature = null;

            if (possibleAttackers.Count > 0)
            {
                creature = possibleAttackers.First.Value;
                possibleAttackers.Remove(creature);
            }

            return creature;
        }

        /// <summary>
        /// Called when the AI's combat phase is over. It is not necessary for the AI
        /// to functon.
        /// </summary>
        public override void PhaseCombatEnd()
        {
            //Do nothing.
        }

        #endregion

        #region methods that need to be moved

        /// <summary>
        /// Returns a linked list of ManaColors that represent the mana that would
        /// be avaliable if every basic land in a CardPool were to be tapped.
        /// </summary>
        /// <param name="activePool">CardPool containing lands.</param>
        /// <returns>Avaliable mana pool.</returns>
        public LinkedList<ManaColor> GetProjectedManaPool(CardPool activePool)
        {
            LinkedList<ManaColor> avaliableMana = new LinkedList<ManaColor>();

            foreach (ICard card in activePool.Cards)
            {
                if (card is CardLand)
                    avaliableMana.AddLast(card.Colors.First.Value);
            }

            return avaliableMana;
        }

        /// <summary>
        /// Writes the contents of a linked list of ICards to the console. The
        /// number of each card will be counted and the number of cards will
        /// be printed once with the name of the card. A prefix may be added.
        /// 
        /// Example ({Forest, Forest, Raging Goblin}, "  ") will displayed:
        ///   2 Forest
        ///   1 Raging Goblin
        /// </summary>
        /// <param name="activePool">Cards to display.</param>
        /// <param name="linePrefix">A string to print before each line.</param>
        public void DisplayCardPoolCounted(CardPool activePool, string linePrefix)
        {
            LinkedList<ICard> undisplayedCards = new LinkedList<ICard>();

            foreach (ICard card in activePool.Cards)
                undisplayedCards.AddLast(card);

            while (undisplayedCards.Count > 0)
            {
                LinkedList<ICard> cardCopies = new LinkedList<ICard>();
                string cardName = undisplayedCards.First.Value.Name;

                foreach (ICard card in undisplayedCards)
                    if (cardName.Equals(card.Name))
                        cardCopies.AddLast(card);

                foreach (ICard card in cardCopies)
                    undisplayedCards.Remove(card);

                System.Console.WriteLine(linePrefix + cardCopies.Count
                                                    + " " + cardName);
            }

        }

        /// <summary>
        /// Displays a list of creature cards on a single line. A title/prefix may
        /// be added. Example ({Forest, Forest, Raging Goblin}, "Att") will display:
        /// Att: Raging Goblin
        /// </summary>
        /// <param name="prefix">Title to display on same line as creatures.</param>
        /// <param name="activePool">CardPool to get creatures from.</param>
        public void DisplayCardPoolCreaturesShort(string prefix, CardPool activePool)
        {
            LinkedList<ICard> sortedCreatures = new LinkedList<ICard>();
            ICard[] cards = null;

            foreach (ICard card in activePool.Cards)
                if (card is CardCreature)
                    sortedCreatures.AddLast(card);

            cards = new ICard[sortedCreatures.Count];
            sortedCreatures.CopyTo(cards, 0);

            System.Console.Write(prefix + ": ");

            if (cards.Length == 0)
            {
                System.Console.WriteLine("N/A");
            }
            else
            {
                System.Console.Write(cards[0].Name);

                for (int x = 1; x < cards.Length; x++)
                    System.Console.Write(", " + cards[x].Name);

                System.Console.WriteLine();
            }
        }

        /// <summary>
        /// Displays a list of strings  on a single line. A title/prefix may be added.
        /// Example ({Forest, Forest, Raging Goblin}, "Att") will display:
        /// Att: Forest, Forest, Raging Goblin
        /// </summary>
        /// <param name="prefix">String then will printed before the cards.</param>
        /// <param name="cardList">List of cards to print.</param>
        public void DisplayStringListShort(string prefix, LinkedList<string> cardList)
        {
            //TODO: Code is similar to DisplayCardPoolCreaturesShort(), in fact it
            //      is identical except that this function's argument is a linked
            //      list of strings instead of a unsorted CardPool. This code needs
            //      to be merged.

            string[] cards = new string[cardList.Count];
            cardList.CopyTo(cards, 0);

            System.Console.Write(prefix + ": ");

            if (cards.Length == 0)
            {
                System.Console.WriteLine("N/A");
            }
            else
            {
                System.Console.Write(cards[0]);

                for (int x = 1; x < cards.Length; x++)
                    System.Console.Write(", " + cards[x]);

                System.Console.WriteLine();
            }
        }

        /// <summary>
        /// Given a linked list of ICards and a specific ManaColor, returns the
        /// number of times that the ManaColor occurs in the cost of the ICards in
        /// the list.
        /// </summary>
        /// <param name="cards">Cards to count cost of.</param>
        /// <param name="color">ManaColor to count in cost.</param>
        /// <returns>Times the ManaColor occurs in cost of cards.</returns>
        public int CountManaCostByColor(LinkedList<ICard> cards, ManaColor color)
        {
            int count = 0;

            foreach (ICard card in cards)
                foreach (ManaColor costColor in card.Cost)
                    if (costColor == color)
                        count++;

            return count;
        }

        /// <summary>
        /// Given a linked list of ICards and a specific ManaColor, returns the
        /// number of lands in the list which have the given ManaColor as one of
        /// their colors.
        /// </summary>
        /// <param name="cards">Cards to check for color.</param>
        /// <param name="color">Mana color to check for.</param>
        /// <returns>Number of lands with color.</returns>
        public int CountLandByColor(LinkedList<ICard> cards, ManaColor color)
        {
            int count = 0;

            foreach (ICard card in cards)
                if (card is CardLand && card.Colors.Contains(color))
                    count++;

            return count;
        }

        #endregion
    }

    /// <summary>
    /// This class represents a copy of the state of the game at some point.
    /// 
    /// At this point we track: 1) AI health, hand, permanents, and deck.
    ///                         2) Enemy health, and permanents.
    /// </summary>
    class AIVirtualGameState
    {
        private int aiHealth;
        private CardPool aiHand;
        private CardPool aiPermanents;
        private CardPool aiDeck;

        private int enemyHealth;
        private CardPool enemyPermanents;
        
        /// <summary>
        /// Returns/sets the AI's health in this state.
        /// </summary>
        public int AIHealth
        {
            get { return aiHealth; }
            set { aiHealth = value; }
        }

        /// <summary>
        /// Returns/sets the CardPool of the AI's hand in this state.
        /// </summary>
        public CardPool AIHand
        {
            get { return aiHand; }
            set { aiHand = value; }
        }

        /// <summary>
        /// Returns/sets the CardPool of the AI's permanents in this state.
        /// </summary>
        public CardPool AIPermanents
        {
            get { return aiPermanents; }
            set { aiPermanents = value; }
        }

        /// <summary>
        /// Returns/sets the CardPool of the AI's deck in this state.
        /// </summary>
        public CardPool AIDeck
        {
            get { return aiDeck; }
            set { aiDeck = value; }
        }

        /// <summary>
        /// Returns/sets the enemy's health in this state.
        /// </summary>
        public int EnemyHealth
        {
            get { return enemyHealth; }
            set { enemyHealth = value; }
        }

        /// <summary>
        /// Returns/sets the CardPool of the enemy's permanents in this state.
        /// </summary>
        public CardPool EnemyPermanents
        {
            get { return enemyPermanents; }
            set { enemyPermanents = value; }
        }

        /// <summary>
        /// Returns a clone of this AIVirtualGameState. A clone contains the
        /// same data as the original but has new references. Thus, we can make
        /// changes to a clone of the game state without being concerned that
        /// we chance the actual game state.
        /// 
        /// Note: We do reuse the references for the individual cards stored by
        /// the CardPools since we probably don't have enough memory to clone
        /// them. As long as we don't try changing the cards themselves, 
        /// everything is fine (i.e. we can change the CardPools.)
        /// </summary>
        /// <returns></returns>
        public AIVirtualGameState clone()
        {
            AIVirtualGameState clone = new AIVirtualGameState();

            clone.AIHealth = aiHealth;
            clone.AIHand = aiHand.clone();
            clone.AIPermanents = aiPermanents.clone();
            clone.AIDeck = aiDeck.clone();
            clone.EnemyHealth = enemyHealth;
            clone.EnemyPermanents = enemyPermanents.clone();

            return clone;
        }

    }

    /// <summary>
    /// This class contains a few static functions for use by the AI. In most
    /// cases, functions were moved here so that they would be be isolated from
    /// the Puppet. The isolated functions can be used with AIVirtualGameStates.
    /// </summary>
    class UtilAI
    {
        static public void PredictNextDraw(LinkedList<ICard> completeDeck,
                                           CardPool possibleCards,
                                           CardPool currentHand,
                                           CardPool currentGraveyard)
        {

            //TODO: We also need to remove permanents from the deck.

            float highestChance = 0;
            string highestChanceCard = "UtilAI->PredictNextDraw() ERROR";

            //Reset the remaining deck.
            //TODO: It's faster not to reset and instead change it based on
            //      what dies or is drawn, but then we have to track that stuff.
            CardPool remainDeck = new CardPool(Zone.OTHER);

            //Populate the remaining deck with the complete deck contents.
            foreach (ICard card in completeDeck)
                remainDeck.AddCard(card);

            //The remaining deck cannot contain any card in our hand.
            foreach (ICard card in currentHand.Cards)
                remainDeck.RemoveCard(card);

            //The remaining deck cannot contain any card in our graveyard.
            foreach (ICard card in currentGraveyard.Cards)
                remainDeck.RemoveCard(card);

            //calculate possiblity of drawing cards.
            foreach (ICard card in possibleCards.Cards)
            {
                //Check if any card of that type still exists in our deck.
                if (remainDeck.countCard(card.Name) > 0)
                {
                    float cardChance;

                    cardChance = UtilMath.Combination(remainDeck.countCard(card.Name), 1)
                               / UtilMath.Combination(remainDeck.Cards.Count, 1);

                    //Checks if the chance of drawing this card is greater than
                    //the chance of drawing the previous card and if so, chances
                    //the most likely card to this one.
                    if (cardChance > highestChance)
                    {
                        highestChance = cardChance;
                        highestChanceCard = card.Name;
                    }

                    System.Console.WriteLine("    " + card.Name + " chance is " + cardChance);
                }
            }

            System.Console.WriteLine("    " + highestChanceCard + " will probably be drawn.");
        }
    }

    /// <summary>
    /// This class contains a variety of static helper math functions need by the
    /// AI code. Most of the function are for dealing with probability.
    /// </summary>
    class UtilMath
    {
        /// <summary>
        /// Returns the number of combinations drawn from a set containing
        /// 'n' elements when each combination contains 'r' elements.
        /// </summary>
        /// <param name="n">Set elements.</param>
        /// <param name="r">Combination elements.</param>
        /// <returns>Combinations possible.</returns>
        static public float Combination(int n, int r)
        {
            return Factorial(n) / (Factorial(r) * Factorial(n - r));
        }

        /// <summary>
        /// Returns the factorial of a number per the standard mathematical
        /// definition.
        /// 
        /// Note that although this function produces a whole number, we return a
        /// float instead of int because our usage of factorials requires results
        /// greater than can be stored by an int.
        /// </summary>
        /// <param name="x">Factorial to find.</param>
        /// <returns>Result of factorial.</returns>
        static public float Factorial(int x)
        {
            if (x < 2)
                return 1;
            else
                return x * Factorial(x - 1);
        }

        /// <summary>
        /// Returns the lowest number in a non-empty linked list of floats.
        /// </summary>
        /// <param name="floats">List of floats.</param>
        /// <returns>Lowest float in list.</returns>
        static public float GetLowestFloat(LinkedList<float> floats)
        {
            float lowestFloat = floats.First.Value;

            foreach (float currentFloat in floats)
            {
                if (lowestFloat > currentFloat)
                    lowestFloat = currentFloat;
            }

            return lowestFloat;
        }
    }
}